/**
 * 定义x和y两个整数近似相等：
 * 至多操作两次，选择y的两个数位，进行交换，使得y==x
 * 给定数组A，问近似相等的元素对数
 * 
 * 弄一个计数器，记作C
 * 倒序for每个Ai:
 *    sum += C[Ai]
 *    然后将Ai能够生成的数的cnt加加
 * 
 * Ai能够生成的数：
 * 1. 0次操作，就是自己
 * 2. 1次操作，C(7,2)
 * 3. 2次操作选中3个数，C(7,3) * 2
 * 4. 2次操作选中4个数，C(7, 4) * C(4, 2)
 * 
 * 如果计数器不算时间，总复杂度是
 * O(7 * 5000 * (1 + 70 + 420))
 */
class Solution {
    vector<vector<int>> Vec;
    unordered_map<int, int> Cnt;

public:
    int countPairs(vector<int>& nums) {
        size_t m = 0;
        for(auto i : nums){
            Vec.emplace_back(vector<int>());
            while(i){
                Vec.back().emplace_back(i % 10);
                i /= 10;
            }
            m = max(m, Vec.back().size());
        }  
        for(auto & v : Vec){
            while(v.size() < m){
                v.push_back(0);
            }
            reverse(v.begin(), v.end());
        }
        
        int ans = 0;
        for(int j=nums.size()-1;j>=0;--j){
            int tmp = Cnt[nums[j]];
            ans += tmp;
            proc(nums, j);
        }
        return ans;
    }

    void proc(vector<int>& nums, int idx){
        int val = nums[idx];
        unordered_set<int> flag;
        flag.insert(val);
        Cnt[val] += 1;

        auto & vec = Vec[idx];
        for(int i=0,n=vec.size();i<n;++i)for(int j=i+1;j<n;++j){
            swap(vec[i], vec[j]);
            int t = 0;
            for(auto k : vec){
                t = t * 10 + k;
            }
            auto it = flag.find(t);
            if(it == flag.end()){
                flag.insert(it, t);
                Cnt[t] += 1;
            }
            swap(vec[i], vec[j]);

            for(int k=j+1;k<n;++k){
                int tmp = vec[k];
                vec[k] = vec[j];
                vec[j] = vec[i];
                vec[i] = tmp;

                t = 0;
                for(auto x : vec){
                    t = t * 10 + x;
                }
                it = flag.find(t);
                if(it == flag.end()){
                    flag.insert(it, t);
                    Cnt[t] += 1;
                }           

                tmp = vec[k];
                vec[k] = vec[j];
                vec[j] = vec[i];
                vec[i] = tmp;

                t = 0;
                for(auto x : vec){
                    t = t * 10 + x;
                }
                auto it = flag.find(t);
                if(it == flag.end()){
                    flag.insert(it, t);
                    Cnt[t] += 1;
                }  

                tmp = vec[k];
                vec[k] = vec[j];
                vec[j] = vec[i];
                vec[i] = tmp;

                for(int u=k+1;u<n;++u){
                    vector<int> zhibiao {i, j, k, u};
                    vector<int> zz {0, 0, 1, 1};
                    do{
                        array<int, 4> p {-1, -1, -1, -1};
                        for(int i=0;i<4;++i){
                            if(zz[i]){
                                if(-1 == p[0]) p[0] = i;
                                else p[1] = i;
                            }else{
                                if(-1 == p[2]) p[2] = i;
                                else p[3] = i;
                            }
                        }
                        swap(vec[zhibiao[p[0]]], vec[zhibiao[p[1]]]);
                        swap(vec[zhibiao[p[2]]], vec[zhibiao[p[3]]]);
                        t = 0;
                        for(auto x : vec){
                            t = t * 10 + x;
                        }
                        auto it = flag.find(t);
                        if(it == flag.end()){
                            flag.insert(it, t);
                            Cnt[t] += 1;
                        } 
                        swap(vec[zhibiao[p[0]]], vec[zhibiao[p[1]]]);
                        swap(vec[zhibiao[p[2]]], vec[zhibiao[p[3]]]);
                    }while(next_permutation(zz.begin(), zz.end()));
                    
                } 
            }
        }



    }
};
